class Node:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right 

def is_same(root_A,root_B):
    if not root_B: return True
    if root_A.val!=root_B.val: return False 
    return is_same(root_A.left,root_B.left) and is_same(root_A.right,root_B.right)

def solve(root_A,root_B):
    if not root_A: return False 
    if is_same(root_A,root_B): return True 
    if is_same(root_A.left,root_B) or is_same(root_A.right,root_B): return True 

# def build(lst_pre,lst_in):
#     if len(lst_pre)==0: return None
#     root=Node(lst_pre[0])
#     #root=Node(lst_pre[start_pre])
#     k=lst_in.index(lst_pre[0]) #len_left=k
#     root.left=build(lst_pre[1:k+1],lst_in[:k])
#     root.right=build(lst_pre[k+1:],lst_in[k+1:])
#     return root

def build(lst):
    n=len(lst)
    if n==0: return None
    root=Node(lst[0])
    root.left=build(lst[1:int((n-1)/2)+1])
    root.right=build(lst[int((n-1)/2)+1:])
    return root


def traversal_pre(root):
    if not root: return []
    return [root.val]+traversal_pre(root.left)+traversal_pre(root.right)
def traversal_in(root):
    if not root:return []
    return traversal_in(root.left) + [root.val] + traversal_in(root.right)

# pre_A=list(map(int,input()))
# in_A=list(map(int,input()))
# pre_B=list(map(int,input()))
# in_B=list(map(int,input()))

# pre_A=[8,8,9,2,4,7,7]
# in_A=[9,8,4,2,7,8,7]
# pre_B=[8,9,2]
# in_B=[9,8,2]
# root_A=build(pre_A,in_A)
# print(traversal_pre(root_A),traversal_in(root_A))

root_A=build([8,8,9,None,None,2,4,7,7,None,None,None,None,None,None])
root_B=build([8,9,2])
# root_A=build(pre_A,in_A)
# root_B=build(pre_B,in_B)
print(traversal_pre(root_A),traversal_in(root_A),traversal_pre(root_B),traversal_in(root_B))
print(solve(root_A,root_B))
    

